package top.minuy.structure.graph.route.euler;

import top.minuy.structure.graph.cc.bfs.CC;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 在有向图中，找出一条欧拉回路，Hierholzer算法
 *
 * @author Minuy
 * @time 10:40
 * @date 2021/11/27
 */
public class DirectedEulerLoop {

    private Graph g;
    private boolean hasEulerLoop;
    List<Integer> eulerLoop;

    public DirectedEulerLoop(Graph g) {

        if (!g.isDirected()){
            throw new IllegalArgumentException("DirectedEulerLoop only works in directed graph.");
        }

        this.g = g;
        eulerLoop = new ArrayList<>();

        // TODO 有向图的联通分量比较特别，假设是联通的先
   /*     CC cc = new CC(g);
        if (cc.CCCount() == 1) {
            hasEulerLoop = checkEulerLoop();
        }


*/
        hasEulerLoop = checkEulerLoop();

        if (!hasEulerLoop) {
            return;
        }

        {
            Graph graph = g.clone();
            ArrayList<Integer> stack = new ArrayList<>();
            int v = 0;
            stack.add(v);
            while (!stack.isEmpty()) {
                if (graph.outdegree(v) > 0) {
                    // 走过之后再加（因为开头一个0，最终回到0，所以是两遍）
                    stack.add(v); // 入栈
                    int w = graph.adj(v).iterator().next();
                    // stack.add(w); // 这边就少加了一个0，而且还不知道这个点还有没有度可用
                    graph.removeEdge(v, w); // 有方向 v -> w
                    v = w;
                } else {
                    eulerLoop.add(v);
                    v = stack.remove(stack.size() - 1); // 出栈
                    // eulerLoop.add(v);  // 在这里添加就添加到退回的那个点了，导致重复
                }
            }

            // 有向图，有方向，所以要恢复原来的顺序
            Collections.reverse(eulerLoop);

        }
    }

    /**
     * 获取欧拉回路
     *
     * @return Iterable<Integer> 欧拉回路可迭代对象
     * @author Minuy
     * @date 2021/11/24 22:58
     */
    public Iterable<Integer> loop() {
        return eulerLoop;
    }

    /**
     * 检测是否存在欧拉回路
     *
     * @return boolean 是否存在欧拉回路
     * @author Minuy
     * @date 2021/11/24 22:16
     */
    private boolean checkEulerLoop() {
        for (int v = 0; v < g.V(); v++) {
            // 如果发现一个顶点的出度和入度不同，那肯定不存在欧拉回路了
            if (g.indegree(v) != g.outdegree(v)) {
                return false;
            }
        }
        return true;
    }

//    /**
//     * 检测是否只有一个联通分量
//     *
//     * @return boolean 是一个还是不是
//     * @author Minuy
//     * @date 2021/11/24 22:17
//     */
//    private boolean checkCC() {
//        boolean[] isVisited = new boolean[g.V()];
//
//        int v = 0, cnt = 0;
//        ArrayList<Integer> queue = new ArrayList<>();
//        queue.add(v);
//        isVisited[v] = true;
//        cnt++;
//        while (!queue.isEmpty()) {
//            v = queue.remove(0);
//            for (int w : g.adj(v)) {
//                if (!isVisited[w]) {
//                    queue.add(w);
//                    isVisited[w] = true;
//                    cnt++;
//                }
//            }
//        }
//
//        // 如果只有一个联通分量
//        if (cnt == g.V()) {
//            return true;
//        }
//        return false;
//    }

    /**
     * 查询是否存在欧拉回路
     *
     * @return boolean 是否存在欧拉回路
     * @author Minuy
     * @date 2021/11/24 22:18
     */
    public boolean hasEulerLoop() {
        return hasEulerLoop;
    }

    @Override
    public String toString() {
        return hasEulerLoop + " : " + eulerLoop;
    }
}
